// bus.h
//
// Definitions for Bus, needed to model bus and arbitration
//
//

#ifndef __BUS_H__
#define __BUS_H__

#include "base/Entity.h"
#include "base/MemoryRequest.h"
#include "base/Request.h"
#include "base/RawFlushRequest.h"
#include "base/SnoopACK.h"
#include "base/SnoopResponse.h"
#include "base/StatisticsCollection.h"
#include "util/List.h"
#include "util/Logger.h"
#include "util/Map.h"
#include "util/PriorityQueue.h"

class Bus;

class BufferSlot {
  public:
    NEW_DELETE_OPERATORS_H(BufferSlot,NoSuper);  
    BufferSlot (Packet* _pk, Time _arbTime, uint _numResponse, Bus* _bus, Logger* b) {
        pk = _pk;
        arbTime = _arbTime;
        numResponse = _numResponse;
        ready = (numResponse == 0);
        flag = RESPONSE_NO_SNOOP_RESPONSE;
        bus = _bus;
        logger = b;
    }

    ~BufferSlot () { }

    bool isReady () {
        return ready;
    }

    Packet* getPacket () {
        return pk;
    }

    void setPacket (Packet* _pk) {
        pk= _pk;
    }
    
    ResponseFlag getFlag () {
        return flag;
    }

    Time getArbTime () {
        return arbTime;
    }

    bool match (Packet* _pk) {
        return pk == _pk;
    }
    
    void recordACK (SnoopACK* res) {
        numResponse--;
   
        // If a cache overflows speculative metadata then it can
        // potentially decide to respond to any snoop request.  These
        // responses might be correct or they might be false
        // positives.  They can only be NACK_ABORT, NACK_CONFLICT, or
        // NACK_RETRY.  We can conclude that they are false positives
        // if another cache responds SNOOP_RESPONSE, because that
        // means the other cache already has a validated M line, which
        // would already have been prevented if the NACK was real.

        // NACK_SNAPSHOT_DATA is used when a load-from-snapshot is
        // issued so that the memory won't try to update itself with
        // the returned old data.  It should come from only a single
        // processor, since at most one log entry usable for snapshot
        // can have been created without reading the old data using
        // load-from-snapshot, and if a log entry observes a response
        // to load-from-snapshot that is of type NACK_SDATA it will
        // skip making the log.  Caches must also respond to
        // fetch-from-snapshot loads with current data from the cache
        // because if there is no log entry that is the correct value,
        // so we might get a NACK_SDATA and a SNOOP_RESP.

        // NACK_CONFLICT means that a conflict has occurred but the
        // defender is leaving it up to the attacker how to response.
        // In this sense it is a superposition of the NACK_ABORT,
        // NACK_BLOCK, and NACK_RETRY responses, because the attacker
        // (requester) can choose to abort, wait for commit, or retry.
        // Some mechanism should probably be in place so that on retry
        // the defender will make a different choice.  This means that
        // NACK_CONFLICT is part of a conversation that can
        // potentially take an extra one-way trip from the attacker to
        // the defender so that the attacker can decide how to resolve
        // the conflict.
       
        // - If the defender (who notices the conflict) decides to
        // abort itself then no special snoop response is needed
        // (NACK_RETRY is likely so that the attacker will wait for
        // the defender to finish abort).

        // - If the defender decides to abort the attacker then it
        // will response with NACK_ABORT and the attacker has no
        // choice.

        // - If the defender decides that the attacker should wait for
        // it to commit it will respond with NACK_BLOCK.  This only
        // makes sense for certain conflicts.  Whoever decides on
        // blocking must detect deadlocks.

        // - If the defender decides that the attacker should choose
        // the action it response with NACK_CONFLICT.  If the attacker
        // then decides to abort itself it then does so, no extra
        // messages.

        // - If the defender returns NACK_CONFLICT and the attacker
        // decides to abort the defender, it reissues the conflicting
        // LoadRequest with some additional information that causes
        // the defender's conflict resolution policy to decide on
        // abort.  This additional information could be a retry count,
        // a priority, or a bit that indicates the attacker's
        // intention to not abort itself.  It could also contain the
        // transaction ID of the defender to prevent unwarranted
        // aggression toward a new defending transaction.

        // If there are no false positives then the transition table is:
        //                                   incoming res->getFlags()
        // existing        ++------------+---------------+------------+------------+------------+---------------+------------+
        //  flag           || SNOOP_RESP | SNOOP_NO_RESP | NACK_ABORT | NACK_BLOCK | NACK_RETRY | NACK_CONFLICT | NACK_SDATA |
        // +===============++============+===============+============+============+============+===============+============+
        // | SNOOP_RESP    ||  invalid   |  SNOOP_RESP   |  invalid   |  invalid   |  invalid   |    invalid    | NACK_SDATA |
        // +---------------++------------+---------------+------------+------------+------------+---------------+------------+
        // | SNOOP_NO_RESP || SNOOP_RESP | SNOOP_NO_RESP | NACK_ABORT | NACK_BLOCK | NACK_RETRY | NACK_CONFLICT | NACK_SDATA |
        // +---------------++------------+---------------+------------+------------+------------+---------------+------------+
        // | NACK_ABORT    ||  invalid   |  NACK_ABORT   |  invalid   |  invalid   |  invalid   |    invalid    |  invalid   |
        // +---------------++------------+---------------+------------+------------+------------+---------------+------------+
        // | NACK_BLOCK    ||  invalid   |  NACK_BLOCK   |  invalid   |  invalid   |  invalid   |    invalid    |  invalid   |
        // +---------------++------------+---------------+------------+------------+------------+---------------+------------+
        // | NACK_RETRY    ||  invalid   |  NACK_RETRY   |  invalid   |  invalid   |  invalid   |    invalid    |  invalid   |
        // +---------------++------------+---------------+------------+------------+------------+---------------+------------+
        // | NACK_CONFLICT ||  invalid   | NACK_CONFLICT |  invalid   |  invalid   |  invalid   |    invalid    |  invalid   |
        // +---------------++------------+---------------+------------+------------+------------+---------------+------------+
        // | NACK_SDATA    || NACK_SDATA |  NACK_SDATA   |  invalid   |  invalid   |  invalid   |    invalid    |  invalid   |
        // +---------------++------------+---------------+------------+------------+------------+---------------+------------+

        // Basically any response other than NO_RESPONSE indicates a
        // tag match (log match if the request was marked
        // fetch-from-snapshot) against a cache line marked M, so if
        // we get two responses other than NO_RESPONSE then something
        // went wrong.

        // NACK_SDATA doesn't enter the false positive picture because
        // it only arises in response to fetch-from-snapshot loads,
        // and those loads do not cause violations.

        // Once false positives enter the picture, we get
        //                                   incoming res->getFlags()
        // existing        ++------------+---------------+------------+------------+---------------+---------------+------------+
        //  flag           || SNOOP_RESP | SNOOP_NO_RESP | NACK_ABORT | NACK_BLOCK |  NACK_RETRY   | NACK_CONFLICT | NACK_SDATA |
        // +===============++============+===============+============+============+===============+===============+============+
        // | SNOOP_RESP    ||  invalid   |  SNOOP_RESP   | SNOOP_RESP*| SNOOP_RESP*|  SNOOP_RESP*  |  SNOOP_RESP*  | NACK_SDATA |
        // +---------------++------------+---------------+------------+------------+---------------+---------------+------------+
        // | NO_SNOOP_RESP || SNOOP_RESP | NO_SNOOP_RESP | NACK_ABORT | NACK_BLOCK |  NACK_RETRY   | NACK_CONFLICT | NACK_SDATA |
        // +---------------++------------+---------------+------------+------------+---------------+---------------+------------+
        // | NACK_ABORT    || SNOOP_RESP*|  NACK_ABORT   | NACK_ABORT#| NACK_ABORT#|  NACK_ABORT#  |  NACK_ABORT#  |  invalid   |
        // +---------------++------------+---------------+------------+------------+---------------+---------------+------------+
        // | NACK_BLOCK    || SNOOP_RESP*|  NACK_BLOCK   | NACK_ABORT#| NACK_BLOCK#|  NACK_BLOCK#  |  NACK_BLOCK#  |  invalid   |
        // +---------------++------------+---------------+------------+------------+---------------+---------------+------------+
        // | NACK_RETRY    || SNOOP_RESP*|  NACK_RETRY   | NACK_ABORT#| NACK_BLOCK#|  NACK_RETRY#  | NACK_CONFLICT#|  invalid   |
        // +---------------++------------+---------------+------------+------------+---------------+---------------+------------+
        // | NACK_CONFLICT || SNOOP_RESP*| NACK_CONFLICT | NACK_ABORT#| NACK_BLOCK#| NACK_CONFLICT#| NACK_CONFLICT#|  invalid   |
        // +---------------++------------+---------------+------------+------------+---------------+---------------+------------+
        // | NACK_SDATA    || NACK_SDATA |  NACK_SDATA   |  invalid   |  invalid   |    invalid    |    invalid    |  invalid   |
        // +---------------++------------+---------------+------------+------------+---------------+---------------+------------+
        // Where * and # are transitions in which we can conclude that
        // a false positive NACK_ABORT, NACK_BLOCK, NACK_RETRY, or
        // NACK_CONFLICT was generated.  In * there is only one
        // response that might be the false positive and so we decide
        // on SNOOP_RESPONSE, where in # we can't tell which response
        // was the false positive so we use a precedence rule
        // NACK_ABORT >> NACK_BLOCK >> NACK_CONFLICT >> NACK_RETRY.
       
        // We could add a configuration variable somewhere that lets
        // us know if our configured system has the potential for
        // false positives, which would allow tighter checking of
        // protocol behavior.  For now we just note that all valid
        // transitions when there are no false positives are the same
        // as the valid transitions when false positives occur, so we
        // assume false positives all the time.

        if (res->getFlag() == RESPONSE_NACK_SNAPSHOT_DATA || flag == RESPONSE_NACK_SNAPSHOT_DATA) {
            // invalid if we have anything except one NACK_SDATA and one SNOOP_RESPONSE or NO_SNOOP_RESPONSE
            ASSERT(res->getFlag() == RESPONSE_SNOOP_RESPONSE || flag == RESPONSE_SNOOP_RESPONSE ||
                   res->getFlag() == RESPONSE_NO_SNOOP_RESPONSE || flag == RESPONSE_NO_SNOOP_RESPONSE);
            flag = RESPONSE_NACK_SNAPSHOT_DATA;
        }
        else if (res->getFlag() == RESPONSE_SNOOP_RESPONSE || flag == RESPONSE_SNOOP_RESPONSE) {
            // invalid if we have two responses
            ASSERT(res->getFlag() != RESPONSE_SNOOP_RESPONSE || flag != RESPONSE_SNOOP_RESPONSE);
            flag = RESPONSE_SNOOP_RESPONSE;
        }
        else if (res->getFlag() == RESPONSE_NACK_ABORT || flag == RESPONSE_NACK_ABORT) {
            flag = RESPONSE_NACK_ABORT;
        }
        else if (res->getFlag() == RESPONSE_NACK_BLOCK || flag == RESPONSE_NACK_BLOCK) {
            flag = RESPONSE_NACK_BLOCK;
        }
        else if (res->getFlag() == RESPONSE_NACK_CONFLICT || flag == RESPONSE_NACK_CONFLICT) {
            flag = RESPONSE_NACK_CONFLICT;
        }
        else if (res->getFlag() == RESPONSE_NACK_RETRY || flag == RESPONSE_NACK_RETRY) {
            flag = RESPONSE_NACK_RETRY;
        }
        else {
            ASSERT(res->getFlag() == RESPONSE_NO_SNOOP_RESPONSE && flag == RESPONSE_NO_SNOOP_RESPONSE);
        }
        
        if (numResponse == 0) {
            ready = true;
        }        
    }
    
  private:
    Packet* pk;
    Time arbTime;
    uint numResponse;
    Bus* bus;
    Logger* logger;

    // this variable goes to false while it is waiting for snoop response.
    bool ready;
    ResponseFlag flag;
};

class SplitBus;

// class Bus
//
// Models the bus and the arbiter. Arbitrates between a set of devices which
// are hard-wired in (all processors + the L2 cache)
//
class Bus : public Entity {
  public:

    // overloaded to force use of CALLOC/FREE
    NEW_DELETE_OPERATORS_H(Bus,Entity);
    Bus (char* name,
         SplitBus* sBus,
         int widthBytes,
         int arbDelay,
         int pipelineLength,
         StatisticsCollection* statsInput, 
         StatisticsCollection* statsOutput, 
         StatisticsCollection* statsQueue, 
         Logger* log);
    virtual ~Bus ();

    // void tick()
    //
    // Tell the bus to take a cycle.
    //
    void tick ();

    void countVotes ();

    // ACCESSORS //
    uint getWidth () { return (uint)width; }
    uint getArbitrationDelay () { return (uint)arbDelay; }

    StatisticsCollection* getInputStatistics () { return statsInput; }
    StatisticsCollection* getOutputStatistics () { return statsOutput; }

    Bucket* bktInputCyclesIdle;
    Bucket* bktInputCyclesArbitration;
    Bucket* bktInputCyclesFirst;
    Bucket* bktInputCyclesFollowing;
    Bucket* bktOutputCyclesIdle;
    Bucket* bktOutputCyclesWaiting;
    Bucket* bktOutputCyclesFirst;
    Bucket* bktOutputCyclesDestBusy;
    Histogram* histQueueOccupancy;
    Histogram* histEntitiesWaitingForDest;
    
    bool busTrace;

  protected:
    Logger*        busLog;
    StatisticsCollection* statsInput;
    StatisticsCollection* statsOutput;
    StatisticsCollection* statsQueue;
    bool            gradualDelivery;
    
    // static physical attributes
    //
    uint           width;
    uint           arbDelay;
    int            bufferSize;
    uint           transferTime;
    uint           startTransferTime;
    Packet* arbitratedPacket;

    bool addedDevice;
    Map<Entity*, List<Packet*>* > packets;
    int packetCount;
    Map<Entity*, List<Packet*>* >::iterator arbRobin;

    bool countVoteHelper (Vector<Bucket*>* buckets);

    void addPacket (Packet*);
    Packet* removePacket (Entity* src);
    Packet* removePacket (List<Packet*>* src);

    Result handle_incoming (Packet* r);
    Result handle_snoopACK (Packet* r);
    Result handle_RawFlushRequest (Packet* r);
    void propagateResponse (Response* resp);
    void flushPacketsInBuffers (RawFlushRequest* r);
    void flushPacketUnderArbitration (RawFlushRequest* r);
    void flushPacketsInForArbitration (RawFlushRequest* r);
    virtual bool isSnooped (Packet* p);
    void broadcastSnoopRequest ();
    void transferArbitratedPacketToBuffer ();
    void pickUpPacketToArbitrate ();
    Result sendOutPacketFromBuffer (BufferSlot* slot);
    Response* getSnoopResult (SnoopResponse* snoopResponse);
    bool hasDirtyLine (SnoopResponse* snoopResponse);
    virtual bool isGraduallyDelivered (Packet *p);
    void calculateTransferTime ();
    void startSnoop ();

    List<BufferSlot*>* packetBuffer;
    SplitBus* sBus;
    
#ifdef BUS_USAGE_GRAPH
    int   recentBytes;
#endif
};

#endif // __BUS_H__
